package com.wzh.test.binarytree;

import com.sun.org.apache.xerces.internal.xs.ItemPSVI;

public class BinaryTreeDemo {
    public static void main(String[] args) {
//        HeroNode root = new HeroNode(1, "宋江");
//        HeroNode node02 = new HeroNode(2, "吴用");
//        HeroNode node03 = new HeroNode(3, "卢俊义");
//        HeroNode node04 = new HeroNode(4, "林冲");
//        HeroNode node05 = new HeroNode(5, "公孙胜");
//
//        root.setLeft(node02);
//        root.setRight(node03);
//        node03.setLeft(node04);
//        node03.setRight(node05);
//
//        BinaryTree binaryTree = new BinaryTree();
//        binaryTree.setRoot(root);

//        System.out.println("前序遍历=======================");
//        binaryTree.preOrder();//1,2,3,4,5
//
//        System.out.println("中序遍历======================");
//        binaryTree.middleOrder();//2,1,4,3,5
//
//        System.out.println("后序遍历========================");
//        binaryTree.postOrder();//2,4,5,3,1

        //二叉树-查找指定节点
        //要求
        //1、请编写前序查找，中序查找和后续查找的方法
        //2、并分别使用三种查找算法，查找heroId = 5 的节点
        //3、并分析各种插好方式，分别比较了多少次
        /*
        System.out.println();
        System.out.println("开始前序查找=============");
        HeroNode heroNode1 = binaryTree.preSearch(binaryTree.getRoot(), 5);
        System.out.println("前序查找结果====" + heroNode1);

        System.out.println();
        System.out.println("开始中序查找=============");
        HeroNode heroNode2 = binaryTree.middleSearch(binaryTree.getRoot(), 5);
        System.out.println("中序查找结果====" + heroNode2);

        System.out.println();
        System.out.println("开始后序查找=============");
        HeroNode heroNode3 = binaryTree.postSearch(binaryTree.getRoot(), 5);
        System.out.println("后序查找结果====" + heroNode3);
         */
        /**
         * 二叉树-删除节点
         * 要求
         * 1、如果删除的节点是叶子节点，则删除该节点
         * 2、如果删除的节点是非叶子节点，则删除该子树
         * 3、测试，删除5号叶子节点和3号子树
         */
//        HeroNode delNode = binaryTree.preSearch(root,5);
//        binaryTree.delNode(root,delNode);
//        System.out.println("删除之后的数据===============");
//        binaryTree.preOrder();


        //===========开始做顺序存储二叉树=================
        /**
         * 顺序存储二叉树的特点：
         * 1、顺序二叉树通常只考虑完全二叉树
         * 2、第n个元素的左子节点为2*n+1
         * 3、第n个元素的右子节点为2*n+2
         * 4、第n个元素的父节点为(n-1)/2
         * 5、n：表示二叉树中的第n个元素（按0开始编号）
         */
        HeroNode node01 = new HeroNode(1,"宋江");
        HeroNode node02 = new HeroNode(2,"卢俊义");
        HeroNode node03 = new HeroNode(3,"吴用");
        HeroNode node04 = new HeroNode(4,"公孙胜");
        HeroNode node05 = new HeroNode(5,"关胜");
        HeroNode node06 = new HeroNode(6,"林冲");
        HeroNode node07 = new HeroNode(7,"秦明");
        node01.setLeft(node02);
        node01.setRight(node03);
        node02.setLeft(node04);
        node02.setRight(node05);
        node03.setLeft(node06);
        node03.setRight(node07);

        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setRoot(node01);
        System.out.println("前序打印二叉树");
        node01.preOrder();

        //定义一个数组
        HeroNode[] heroNodes = new HeroNode[7];
        copyTreeToArray(node01,heroNodes,0);



    }

    private static void copyTreeToArray(HeroNode node01, HeroNode[] heroNodes, int level) {

    }
}

class BinaryTree {
    private HeroNode root;

    public HeroNode getRoot() {
        return root;
    }

    public boolean delNode(HeroNode parentNode,HeroNode delNode){
        boolean result = false;
        if(parentNode.getLeft() == delNode){
            parentNode.setLeft(null);
            result = true;
        }else if(parentNode.getRight() == delNode){
            parentNode.setRight(null);
            result = true;
        }
        if(!result && parentNode.getLeft() != null){
            result = delNode(parentNode.getLeft(),delNode);
        }
        if(!result && parentNode.getRight() != null){
            result = delNode(parentNode.getRight(),delNode);
        }
        return result;
    }


    public HeroNode preSearch(HeroNode node, int id) {
        HeroNode tmpNode = null;
        System.out.println(node);
        if (node.getId() == id) {
            tmpNode = node;
        }
        if(tmpNode == null && node.getLeft() != null){
            tmpNode = preSearch(node.getLeft(),id);
        }
        if(tmpNode == null && node.getRight() != null){
            tmpNode = preSearch(node.getRight(),id);
        }
        return tmpNode;
    }

    public HeroNode middleSearch(HeroNode node, int id) {
        HeroNode tmpNode = null;
        if(node.getLeft() != null){
            tmpNode = middleSearch(node.getLeft(),id);
        }
        if(tmpNode == null){
            System.out.println(node);
            if (node.getId() == id) {
                tmpNode = node;
            }
        }
        if(tmpNode == null && node.getRight() != null){
            tmpNode = middleSearch(node.getRight(),id);
        }
        return tmpNode;
    }

    public HeroNode postSearch(HeroNode node,int id){
        HeroNode tmpNode = null;
        if(node.getLeft() != null){
            tmpNode = postSearch(node.getLeft(),id);
        }
        if(tmpNode == null && node.getRight() != null){
            tmpNode = postSearch(node.getRight(),id);
        }
        if(tmpNode == null){
            System.out.println(node);
            if(node.getId() == id){
                tmpNode = node;
            }
        }
        return tmpNode;
    }




    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder() {
        this.root.preOrder();
    }

    public void middleOrder() {
        this.root.middleOrder();
    }

    public void postOrder() {
        this.root.postOrder();
    }

}

class HeroNode {
    private int id;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public HeroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    /**
     * 中序遍历
     */
    public void middleOrder() {
        if (this.left != null) {
            this.left.middleOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.middleOrder();
        }

    }

    /**
     * 后续遍历
     */
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }
}